from typing import List


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> list[int]:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i = len(nums1) - 1
        m = m - 1
        n = n - 1

        while n >= 0:
            while m >= 0 and nums1[m] > nums2[n]:
                self.swap(nums1, i, nums1, m)
                m = m - 1
                i = i - 1
            self.swap(nums1, i, nums2, n)
            n = n - 1
            i = i - 1

    def swap(self, nums1, i, nums2, j):
        tmp = nums1[i]
        nums1[i] = nums2[j]
        nums2[j] = tmp


if __name__ == '__main__':
    solu = Solution()
    solu.merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3)
    solu.merge([1], 1, [], 0)
    solu.merge([0], 0, [1], 1)
